/**
 * 
 * 描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 
O
(
n
)
O(n)，空间复杂度 
O
(
1
)
O(1)。
例如：
给出的链表为 
1
→
2
→
3
→
4
→
5
→
N
U
L
L
1→2→3→4→5→NULL, 
m
=
2
,
n
=
4
m=2,n=4,
返回 
1
→
4
→
3
→
2
→
5
→
N
U
L
L
1→4→3→2→5→NULL.

数据范围： 链表长度 
0
<
s
i
z
e
≤
1000
0<size≤1000，
0
<
m
≤
n
≤
s
i
z
e
0<m≤n≤size，链表中每个节点的值满足 
∣
v
a
l
∣
≤
1000
∣val∣≤1000
要求：时间复杂度 
O
(
n
)
O(n) ，空间复杂度 
O
(
n
)
O(n)
进阶：时间复杂度 
O
(
n
)
O(n)，空间复杂度 
O
(
1
)
O(1)


 */

public class 链表内指定区间反转 {
    public static void main(String[] args) {
        
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node.next.next.next.next.next = new ListNode(6);

        ListNode pre = reverseBetween(node, 2, 4);

        System.out.println(pre.toString());
        
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    private static ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here

        if (head == null || m == n) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        // 移动到反转区间的前一个位置
        for (int i = 1; i < m; i++) {
            prev = prev.next;
        }

        ListNode start = prev.next;
        ListNode then = start.next;

        for (int i = m; i < n; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }

        return dummy.next;
    }

    private static class ListNode{

        public int val;
        public ListNode next;

        public ListNode(int val){

            this.val = val;
        }

        public String toString(){

            StringBuilder builder = new StringBuilder();

            builder.append(val);
            builder.append(",");

            ListNode nextNode = next;

            while(null!=nextNode){

                builder.append(nextNode.val);
                builder.append(",");
                nextNode = nextNode.next;
            }
            

            return builder.toString();
        }

    }
}
